import random
import time

class Heap(object):
    ''' 有序堆.'''

    def __init__(self):
        self.__array = [0]
        self.__length = 0

    def push(self, v: int):
        '''插入一个数.

        Args:
            v:待插入的数
        '''
        self.__array.append(v)
        self.__length += 1
        self.__swim(self.__length)

    def pop_max(self) -> int:
        '''返回最大值并从堆中删除.

        Returns:
            最大值

        Raises:
            ValueError: 堆中没有节点时抛出
        '''
        if self.__length < 1:
            raise ValueError("堆中没有节点")

        max = self.__array[1]
        if self.__length > 1:
            self.__array[1] = self.__array.pop()
        self.__length -= 1
        self.__sink(1)

        return max
    
    def __swim(self, k: int):
        '''上浮一个节点.

        Args:
            k:节点索引
        '''
        while k > 1 and self.__less(k//2, k):
            self.__exch(k//2, k)
            k = k//2

    def __sink(self, k: int):
        '''下沉一个节点. 

        Args:
            k:节点索引
        '''
        while 2*k <= self.__length:
            j = 2*k
            if j < self.__length and self.__less(j, j + 1):
                j += 1
            if self.__less(k, j):
                self.__exch(k, j)
                k = j
            else:
                break

    def __less(self, k1: int, k2: int) -> bool:
        '''比较节点大小

        Args: 
            k1:第一个节点索引
            k2:第二个节点索引

        Return:
            布尔值，表示k1节点是否小于k2节点
        '''
        return self.__array[k1] < self.__array[k2]
    
    def __exch(self, k1: int, k2: int):
        '''交换两个节点的值

        Args:
            k1:第一个节点索引
            k2:第二个节点索引            
        '''
        self.__array[k1], self.__array[k2] = self.__array[k2], self.__array[k1]

    def print(self):
            print(self.__array)         
            
if __name__ == "__main__":
    h = Heap()
    
    l = [random.randint(0,50000) for _ in range(50000)]
    l2 = []
    before = time.time()
    for i in l:
        h.push(i)
    for j in range(0, len(l)):
        l2.append(h.pop_max())
    after = time.time()
    print(after - before)